#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int ans = 0;
        int sum = 0;
        unordered_map<int, int> record = { {0,1} };
        for (int e : nums) {
            sum += e;
            int m = (sum % k + k) % k;
            if (record.count(m)) {
                ans += record[m];
            }
            ++record[m];
        }
        return ans;
    }
};